//===--- CanonicalOSSALifetime.cpp - Canonicalize OSSA value lifetimes ----===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
///
/// This top-level API rewrites the extended lifetime of a SILValue:
///
///     bool CanonicalizeOSSALifetime::canonicalizeValueLifetime(SILValue def)
///
/// Each time it's called on a single OSSA value, `def`, it performs three
/// steps:
///
/// 1. Compute "pruned" liveness of def and its copies, ignoring original
///    destroys. Initializes `liveness`.
///
/// 2. Find `def`s final destroy points based on its pruned
///    liveness. Initializes `consumes` and inserts new destroy_value
///    instructions.
///
/// 3. Rewrite `def`s original copies and destroys, inserting new copies where
///    needed. Deletes original copies and destroys and inserts new copies.
///
/// See CanonicalOSSALifetime.h for examples.
///
/// TODO: Enable canonical-ossa-rewrite-borrows to rewrite single-block borrows.
/// Add support for multi-block borrows, load_borrow, and phi by using
/// persistentCopies.
///
/// TODO: If all client passes can maintain block numbers, then the
/// SmallDenseMaps/SetVectors can be replaced with bitsets/sparsesets.
///
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "copy-propagation"

#include "swift/SILOptimizer/Utils/CanonicalOSSALifetime.h"
#include "swift/SIL/DebugUtils.h"
#include "swift/SIL/InstructionUtils.h"
#include "swift/SIL/OwnershipUtils.h"
#include "swift/SILOptimizer/Utils/CFGOptUtils.h"
#include "swift/SILOptimizer/Utils/InstOptUtils.h"
#include "swift/SILOptimizer/Utils/ValueLifetime.h"
#include "llvm/ADT/Statistic.h"

using namespace swift;
using llvm::SmallSetVector;

STATISTIC(NumCopiesEliminated, "number of copy_value instructions removed");
STATISTIC(NumDestroysEliminated,
          "number of destroy_value instructions removed");
STATISTIC(NumCopiesGenerated, "number of copy_value instructions created");
STATISTIC(NumDestroysGenerated, "number of destroy_value instructions created");
STATISTIC(NumUnknownUsers, "number of functions with unknown users");

/// This use-def walk must be consistent with the def-use walks performed
/// within the canonicalizeValueLifetime() implementation.
SILValue CanonicalizeOSSALifetime::getCanonicalCopiedDef(SILValue v) {
  while (auto *copy = dyn_cast<CopyValueInst>(v)) {
    auto def = copy->getOperand();
    if (def.getOwnershipKind() == OwnershipKind::Owned) {
      v = def;
      continue;
    }
    if (auto borrowedVal = BorrowedValue(def)) {
      // Any def's that aren't filtered out here must be handled by
      // computeBorrowLiveness.
      switch (borrowedVal.kind) {
      case BorrowedValueKind::Invalid:
        llvm_unreachable("Using invalid case?!");
      case BorrowedValueKind::SILFunctionArgument:
        return def;
      case BorrowedValueKind::BeginBorrow: {
        return def;
      }
      case BorrowedValueKind::LoadBorrow:
      case BorrowedValueKind::Phi:
        break;
      }
    }
    // This guaranteed value cannot be handled, treat the copy as an owned
    // live range def instead.
    return copy;
  }
  return v;
}

/// The lifetime extends beyond given consuming use. Copy the value.
///
/// This can set the operand value, but cannot invalidate the use iterator.
static void copyLiveUse(Operand *use, InstModCallbacks &instModCallbacks) {
  SILInstruction *user = use->getUser();
  SILBuilderWithScope builder(user->getIterator());

  auto loc = RegularLocation::getAutoGeneratedLocation(user->getLoc());
  auto *copy = builder.createCopyValue(loc, use->get());
  instModCallbacks.createdNewInst(copy);
  instModCallbacks.setUseValue(use, copy);

  ++NumCopiesGenerated;
  LLVM_DEBUG(llvm::dbgs() << "  Copying at last use " << *copy);
}

// TODO: generalize this to handle multiple nondebug uses of the struct_extract.
SILValue swift::convertExtractToDestructure(StructExtractInst *extract,
                                            InstModCallbacks *callbacks) {
  if (!hasOneNonDebugUse(extract))
    return nullptr;

  if (!extract->isFieldOnlyNonTrivialField())
    return nullptr;

  auto *extractCopy =
      dyn_cast<CopyValueInst>(getNonDebugUses(extract).begin()->getUser());
  if (!extractCopy)
    return nullptr;

  SILBuilderWithScope builder(extract);
  auto loc = extract->getLoc();
  auto *copy = builder.createCopyValue(loc, extract->getOperand());
  auto *destructure = builder.createDestructureStruct(loc, copy);
  if (callbacks) {
    callbacks->createdNewInst(copy);
    callbacks->createdNewInst(destructure);
  }

  SILValue nonTrivialResult = destructure->getResult(extract->getFieldIndex());
  assert(!nonTrivialResult->getType().isTrivial(*destructure->getFunction())
         && "field idx mismatch");

  if (callbacks) {
    callbacks->replaceValueUsesWith(extractCopy, nonTrivialResult);
  } else {
    extractCopy->replaceAllUsesWith(nonTrivialResult);
  }
  return nonTrivialResult;
}

//===----------------------------------------------------------------------===//
//                        MARK: Rewrite borrow scopes
//===----------------------------------------------------------------------===//

bool CanonicalizeOSSALifetime::computeBorrowLiveness() {
  auto borrowedVal = BorrowedValue(currentDef);
  if (!borrowedVal) {
    return false;
  }
  switch (borrowedVal.kind) {
  case BorrowedValueKind::Invalid:
    llvm_unreachable("Used invalid");
  case BorrowedValueKind::SILFunctionArgument:
    // For efficiency, function arguments skip liveness.
    return true;
  case BorrowedValueKind::LoadBorrow:
  case BorrowedValueKind::Phi:
    // TODO: Canonicalize load_borrow scope and phi once consolidateBorrowScope
    // can handle persistentCopies.
    return false;
  case BorrowedValueKind::BeginBorrow:
    break;
  }
  if (!canonicalizeBorrowMode)
    return false;

  // Note that there is no need to look through any reborrows. The reborrowed
  // value is considered a separate lifetime for canonicalization. Any copies of
  // the reborrowed value will not be rewritten when canonicalizing the current
  // borrow scope because they are "hidden" behind the reborrow.
  borrowedVal.visitLocalScopeEndingUses([this](Operand *use) {
    liveness.updateForUse(use->getUser(), /*lifetimeEnding*/ true);
    return true;
  });
  return true;
}

// Create a copy for outer uses of the borrow scope introduced by
// currentDef. This copy should only be used by outer uses in the same block
// as the borrow scope.
//
// To use an existing outer copy, we could find its earliest consume. But the
// new copy will immediately canonicalized and a canonical begin_borrow scope
// have no outer uses of its first block.
static CopyValueInst *createOuterCopy(BeginBorrowInst *beginBorrow,
                                      InstModCallbacks &instModCallbacks) {
  SILBuilderWithScope builder(beginBorrow);

  auto loc = RegularLocation::getAutoGeneratedLocation(beginBorrow->getLoc());
  auto *copy = builder.createCopyValue(loc, beginBorrow->getOperand());
  instModCallbacks.createdNewInst(copy);

  ++NumCopiesGenerated;
  LLVM_DEBUG(llvm::dbgs() << "  Outer copy " << *copy);

  return copy;
}

// This def-use traversal is similar to findExtendedTransitiveGuaranteedUses(),
// however, to cover the canonical lifetime, it looks through copies. It also
// considers uses within the introduced borrow scope itself (instead of simply
// visiting the scope-ending uses). It does not, however, look into nested
// borrow scopes uses, since nested scopes are canonicalized independently.
//
// \p useInsts are the potentially outer use instructions. This set will
// be pared down to only the outer uses in the next step.
bool CanonicalizeOSSALifetime::findBorrowScopeUses(
    llvm::SmallPtrSetImpl<SILInstruction *> &useInsts) {
  auto isUserInLiveOutBlock = [&](SILInstruction *user) {
    return (liveness.getBlockLiveness(user->getParent())
            == PrunedLiveBlocks::LiveOut);
    return false;
  };
  auto recordOuterUse = [&](Operand *use) {
    // If the user's block is LiveOut, then it is definitely within the borrow
    // scope, so there's no need to record it.
    if (isUserInLiveOutBlock(use->getUser())) {
      return;
    }
    useInsts.insert(use->getUser());
  };
  defUseWorklist.initialize(currentDef);
  // Avoid revisiting uses because we recurse through
  // struct/destructure. Otherwise the order does not matter.
  while (SILValue value = defUseWorklist.pop()) {
    for (Operand *use : value->getUses()) {
      auto *user = use->getUser();
      // Recurse through copies.
      if (auto *copy = dyn_cast<CopyValueInst>(user)) {
        defUseWorklist.insert(copy);
        continue;
      }
      // Note: debug_value uses are handled like normal uses here. They should
      // be stripped later if required when handling outerCopy or
      // persistentCopies.

      switch (use->getOperandOwnership()) {
      case OperandOwnership::NonUse:
        break;
      case OperandOwnership::TrivialUse:
        llvm_unreachable("this operand cannot handle ownership");

      case OperandOwnership::InteriorPointer:
      case OperandOwnership::ForwardingBorrow:
      case OperandOwnership::EndBorrow:
      case OperandOwnership::Reborrow:
        // Ignore uses that must be within the borrow scope.
        // Rewriting does not look through reborrowed values--it considers them
        // part of a separate lifetime.
        break;

      case OperandOwnership::ForwardingUnowned:
      case OperandOwnership::PointerEscape:
        // Pointer escapes are only allowed if they use the guaranteed value,
        // which means that the escaped value must be confied to the current
        // borrow scope.
        if (use->get().getOwnershipKind() != OwnershipKind::Guaranteed)
          return false;
        break;

      case OperandOwnership::ForwardingConsume:
        // Recurse through destructure, but also record them as an outer
        // use. Note that they will consider to be outer uses even if they are
        // within this scope as long as any of their transitively uses our
        // outside the scope.
        //
        // FIXME: handle all ForwardingOperands.
        recordOuterUse(use);
        for (auto result : user->getResults()) {
          if (result.getOwnershipKind() == OwnershipKind::Owned) {
            defUseWorklist.insert(result);
          }
        }
        break;

      case OperandOwnership::InstantaneousUse:
      case OperandOwnership::UnownedInstantaneousUse:
      case OperandOwnership::BitwiseEscape:
      case OperandOwnership::DestroyingConsume:
        recordOuterUse(use);
        break;
      case OperandOwnership::Borrow:
        BorrowingOperand borrowOper(use);
        assert(borrowOper && "BorrowingOperand must handle OperandOwnership");
        recordOuterUse(use);
        // For borrows, record the scope-ending instructions in addition to the
        // borrow instruction outer use points. The logic below to check whether
        // a borrow scope is an outer use must visit the same set of uses.
        borrowOper.visitExtendedScopeEndingUses([&](Operand *endBorrow) {
          if (!isUserInLiveOutBlock(endBorrow->getUser())) {
            useInsts.insert(endBorrow->getUser());
          }
          return true;
        });
        break;
      }
    } // end switch OperandOwnership
  }   // end def-use traversal

  return true;
}

void CanonicalizeOSSALifetime::filterOuterBorrowUseInsts(
    llvm::SmallPtrSetImpl<SILInstruction *> &outerUseInsts) {
  auto *beginBorrow = cast<BeginBorrowInst>(currentDef);
  SmallVector<SILInstruction *, 4> scopeEndingInsts;
  BorrowedValue(beginBorrow).getLocalScopeEndingInstructions(scopeEndingInsts);
  blockWorklist.clear();
  // Remove outer uses that occur before the end of the borrow scope by
  // reverse iterating from the end_borrow.
  auto scanBlock = [&](SILBasicBlock *bb, SILBasicBlock::iterator endIter) {
    auto beginIter = bb->begin();
    if (bb == beginBorrow->getParent()) {
      beginIter = std::next(beginBorrow->getIterator());
    } else {
      blockWorklist.insert(bb);
    }
    for (auto instIter = endIter; instIter != beginIter;) {
      --instIter;
      outerUseInsts.erase(&*instIter);
    }
  };
  for (auto *scopeEnd : scopeEndingInsts) {
    scanBlock(scopeEnd->getParent(), std::next(scopeEnd->getIterator()));
  }
  // This worklist is also a visited set, so we never pop the entries.
  while (auto *bb = blockWorklist.pop()) {
    for (auto *predBB : bb->getPredecessorBlocks()) {
      scanBlock(predBB, predBB->end());
    }
  }
}

// Repeat the same def-use traversal as findBorrowScopeUses(). This time,
// instead of recording all the uses, rewrite the operands of outer uses,
// record consumingUses, and add forwarding operations to the outerUseInsts if
// they have transitive outer uses.
//
// Recurse through forwarded consumes, but don't revisit uses. Once an outer
// use it visited, it marks its incoming operand as an outer use.
//
// Return true if any outer uses were found and rewritten.
void CanonicalizeOSSALifetime::rewriteOuterBorrowUsesAndFindConsumes(
    SILValue incomingValue,
    llvm::SmallPtrSetImpl<SILInstruction *> &outerUseInsts) {

  SILValue newIncomingValue =
      (incomingValue == currentDef) ? outerCopy : incomingValue;

  // Outer uses specific to the current incomingValue
  SmallVector<SILInstruction *, 4> currentOuterUseInsts;
  SmallVector<Operand *, 4> consumingUses;
  SmallPtrSet<SILInstruction *, 4> unclaimedConsumingUsers;

  auto rewriteOuterUse = [&](Operand *use) {
    LLVM_DEBUG(llvm::dbgs() << "  Use of outer copy " << *use->getUser());
    instModCallbacks.setUseValue(use, newIncomingValue);
    currentOuterUseInsts.push_back(use->getUser());
    outerUseInsts.insert(incomingValue->getDefiningInstruction());
    if (use->isLifetimeEnding()) {
      consumingUses.push_back(use);
      unclaimedConsumingUsers.insert(use->getUser());
    }
  };
  // defUseWorklist is used recursively here
  unsigned defUseStart = defUseWorklist.size();
  defUseWorklist.insert(incomingValue);
  while (defUseStart < defUseWorklist.size()) {
    SILValue value = defUseWorklist.pop();
    // Gather the uses before updating any of them.
    SmallVector<Operand *, 4> uses(value->getUses());
    for (Operand *use : uses) {
      auto *user = use->getUser();
      // Transitively poke through copies.
      if (auto *copy = dyn_cast<CopyValueInst>(user)) {
        defUseWorklist.insert(copy);
        continue;
      }
      // Note: debug_value uses are handled like normal uses here. They should
      // be stripped later if required when handling outerCopy or
      // persistentCopies.

      switch (use->getOperandOwnership()) {
      case OperandOwnership::NonUse:
      case OperandOwnership::TrivialUse:
      case OperandOwnership::InteriorPointer:
      case OperandOwnership::ForwardingBorrow:
      case OperandOwnership::EndBorrow:
      case OperandOwnership::Reborrow:
      case OperandOwnership::ForwardingUnowned:
      case OperandOwnership::PointerEscape:
        break;

      case OperandOwnership::ForwardingConsume:
        // FIXME: Need unit tests for various forwarding operations.
        //
        // Handles:
        //   Enum, SelectValue, InitExistential, MarkDependence
        //   Struct, Tuple
        //   DestructureStruct, DestructureTuple
        //   Various reference casts,
        //   SelectEnum, SwitchEnum, CheckCastBranch
        if (OwnershipForwardingMixin::isa(user->getKind())) {
          for (auto result : user->getResults()) {
            if (result.getOwnershipKind() != OwnershipKind::Owned)
              continue;

            // Process transitive users and add this destructure to
            // outerUseInsts if any outer uses were found.
            rewriteOuterBorrowUsesAndFindConsumes(result, outerUseInsts);
            if (outerUseInsts.count(user)) {
              rewriteOuterUse(use);
            }
          }
          continue;
        }
        // Calls and unrecognized forwarding consumes are end points.
        LLVM_FALLTHROUGH;

      case OperandOwnership::InstantaneousUse:
      case OperandOwnership::UnownedInstantaneousUse:
      case OperandOwnership::BitwiseEscape:
      case OperandOwnership::DestroyingConsume:
        if (outerUseInsts.count(use->getUser())) {
          rewriteOuterUse(use);
        }
        break;
      case OperandOwnership::Borrow:
        BorrowingOperand borrowOper(use);
        assert(borrowOper && "BorrowingOperand must handle OperandOwnership");

        // For borrows, record the scope-ending instructions in addition to the
        // borrow instruction outer use points.
        if (outerUseInsts.count(use->getUser())
            || !borrowOper.visitExtendedScopeEndingUses([&](Operand *endScope) {
                 return !outerUseInsts.count(endScope->getUser());
               })) {
          rewriteOuterUse(use);
        }
        break;
      }
    }  // end switch OperandOwnership
  }    // end def-use traversal

  // Insert a destroy on the outer copy's or forwarding consume's lifetime
  // frontier, or claim an existing consume.
  ValueLifetimeAnalysis lifetimeAnalysis(
      newIncomingValue.getDefiningInstruction(), currentOuterUseInsts);
  ValueLifetimeBoundary boundary;
  lifetimeAnalysis.computeLifetimeBoundary(boundary);

  for (auto *boundaryEdge : boundary.boundaryEdges) {
    if (DeadEndBlocks::triviallyEndsInUnreachable(boundaryEdge))
      continue;
    auto insertPt = boundaryEdge->begin();
    auto *dvi = SILBuilderWithScope(insertPt).createDestroyValue(
        insertPt->getLoc(), newIncomingValue);
    instModCallbacks.createdNewInst(dvi);
  }

  for (SILInstruction *lastUser : boundary.lastUsers) {
    if (unclaimedConsumingUsers.erase(lastUser))
        continue;

    SILBuilderWithScope::insertAfter(lastUser, [&](SILBuilder &b) {
      auto *dvi = b.createDestroyValue(lastUser->getLoc(), newIncomingValue);
      instModCallbacks.createdNewInst(dvi);
    });
  }
  // Add copies for consuming users of newIncomingValue.
  for (auto *use : consumingUses) {
    // If the user is still in the unclaimedConsumingUsers set, then it does not
    // end the outer copy's lifetime and therefore requires a copy. Only one
    // operand can be claimed as ending the lifetime, so return its user to the
    // unclaimedConsumingUsers set after skipping the first copy.
    auto iterAndInserted = unclaimedConsumingUsers.insert(use->getUser());
    if (!iterAndInserted.second) {
      copyLiveUse(use, instModCallbacks);
    }
  }
}

// If this succeeds, then all uses of the borrowed value outside the borrow
// scope will be rewritten to use an outer copy, and all remaining uses of the
// borrowed value will be confined to the borrow scope.
//
// TODO: Canonicalize multi-block borrow scopes, load_borrow scope, and phi
// borrow scopes by adding one copy per block to persistentCopies for
// each block that dominates an outer use.
bool CanonicalizeOSSALifetime::consolidateBorrowScope() {
  if (isa<SILFunctionArgument>(currentDef)) {
    return true;
  }
  // getCanonicalCopiedDef ensures that if currentDef is a guaranteed value,
  // then it is a borrow scope introducer.
  assert(BorrowedValue(currentDef).isLocalScope());

  // Gather all potential outer uses before rewriting any to avoid scanning any
  // basic block more than once.
  llvm::SmallPtrSet<SILInstruction *, 8> outerUseInsts;
  if (!findBorrowScopeUses(outerUseInsts))
    return false;

  filterOuterBorrowUseInsts(outerUseInsts);
  if (outerUseInsts.empty()) {
    return true;
  }
  this->outerCopy =
      createOuterCopy(cast<BeginBorrowInst>(currentDef), instModCallbacks);

  defUseWorklist.clear();
  rewriteOuterBorrowUsesAndFindConsumes(currentDef, outerUseInsts);
  return true;
}

//===----------------------------------------------------------------------===//
//                    MARK: Step 1. Compute pruned liveness
//===----------------------------------------------------------------------===//

bool CanonicalizeOSSALifetime::computeCanonicalLiveness() {
  defUseWorklist.initialize(currentDef);
  while (SILValue value = defUseWorklist.pop()) {
    for (Operand *use : value->getUses()) {
      auto *user = use->getUser();

      // Recurse through copies.
      if (auto *copy = dyn_cast<CopyValueInst>(user)) {
        defUseWorklist.insert(copy);
        continue;
      }
      // Handle debug_value instructions separately.
      if (pruneDebugMode) {
        if (auto *dvi = dyn_cast<DebugValueInst>(user)) {
          // Only instructions potentially outside current pruned liveness are
          // interesting.
          if (liveness.getBlockLiveness(dvi->getParent())
              != PrunedLiveBlocks::LiveOut) {
            recordDebugValue(dvi);
          }
          continue;
        }
      }
      switch (use->getOperandOwnership()) {
      case OperandOwnership::NonUse:
        break;
      case OperandOwnership::TrivialUse:
        llvm_unreachable("this operand cannot handle ownership");

      // Conservatively treat a conversion to an unowned value as a pointer
      // escape. Is it legal to canonicalize ForwardingUnowned?
      case OperandOwnership::ForwardingUnowned:
      case OperandOwnership::PointerEscape:
        return false;
      case OperandOwnership::InstantaneousUse:
      case OperandOwnership::UnownedInstantaneousUse:
      case OperandOwnership::BitwiseEscape:
        liveness.updateForUse(user, /*lifetimeEnding*/ false);
        break;
      case OperandOwnership::ForwardingConsume:
        recordConsumingUse(use);
        liveness.updateForUse(user, /*lifetimeEnding*/ true);
        break;
      case OperandOwnership::DestroyingConsume:
        // destroy_value does not force pruned liveness (but store etc. does).
        if (!isa<DestroyValueInst>(user)) {
          liveness.updateForUse(user, /*lifetimeEnding*/ true);
        }
        recordConsumingUse(use);
        break;
      case OperandOwnership::Borrow:
        if (!liveness.updateForBorrowingOperand(use))
          return false;
        break;
      case OperandOwnership::InteriorPointer:
      case OperandOwnership::ForwardingBorrow:
      case OperandOwnership::EndBorrow:
      case OperandOwnership::Reborrow:
        llvm_unreachable("operand kind cannot take an owned value");
      }
    }
  }
  return true;
}

// Return true if \p inst is an end_access whose access scope overlaps the end
// of the pruned live range. This means that a hoisted destroy might execute
// within the access scope which previously executed outside the access scope.
//
// Not overlapping (ignored):
//
//     %def
//     use %def     // pruned liveness ends here
//     begin_access // access scope unrelated to def
//     end_access
//
// Overlapping (must extend pruned liveness):
//
//     %def
//     begin_access // access scope unrelated to def
//     use %def     // pruned liveness ends here
//     end_access
//
// Overlapping (must extend pruned liveness):
//
//     begin_access // access scope unrelated to def
//     %def
//     use %def     // pruned liveness ends here
//     end_access
//
bool CanonicalizeOSSALifetime::
endsAccessOverlappingPrunedBoundary(SILInstruction *inst) {
  if (isa<EndUnpairedAccessInst>(inst)) {
    return true;
  }
  auto *endAccess = dyn_cast<EndAccessInst>(inst);
  if (!endAccess) {
    return false;
  }
  auto *beginAccess = endAccess->getBeginAccess();
  SILBasicBlock *beginBB = beginAccess->getParent();
  switch (liveness.getBlockLiveness(beginBB)) {
  case PrunedLiveBlocks::LiveOut:
    // Found partial overlap of the form:
    //     currentDef
    //     beginAccess
    //     br...
    //   bb...
    //     use
    //     endAccess
    return true;
  case PrunedLiveBlocks::LiveWithin:
    // Check for partial overlap of this form where beginAccess and the last use
    // are in the same block:
    //     currentDef
    //     beginAccess
    //     use
    //     endAccess
    if (std::find_if(std::next(beginAccess->getIterator()), beginBB->end(),
                     [this](SILInstruction &nextInst) {
                       return liveness.isInterestingUser(&nextInst)
                         != PrunedLiveness::NonUser;
                     }) != beginBB->end()) {
      // An interesting use after the beginAccess means overlap.
      return true;
    }
    return false;
  case PrunedLiveBlocks::Dead:
    // Check for partial overlap of this form where beginAccess and currentDef
    // are in different blocks:
    //     beginAccess
    //     br...
    //  bb...
    //     currentDef
    //     endAccess
    //
    // Since beginAccess is not within the canonical live range, its access
    // scope overlaps only if there is a path from beginAccess to currentDef
    // that does not pass through endAccess. endAccess is dominated by
    // both currentDef and begin_access. Therefore, such a path only exists if
    // beginAccess dominates currentDef.
    DominanceInfo *domInfo = dominanceAnalysis->get(inst->getFunction());
    return domInfo->properlyDominates(beginAccess->getParent(),
                                      getCurrentDef()->getParentBlock());
  }
  llvm_unreachable("covered switch");
}

// Find all overlapping access scopes and extend pruned liveness to cover them:
//
// This may also unnecessarily, but conservatively extend liveness over some
// originally overlapping access, such as:
//
//     begin_access // access scope unrelated to def
//     %def
//     use %def
//     destroy %def
//     end_access
//
// Or:
//
//     %def
//     begin_access // access scope unrelated to def
//     use %def
//     destroy %def
//     end_access
//
// To minimize unnecessary lifetime extension, only search for end_access
// within dead blocks that are backward reachable from an original destroy.
//
// Note that lifetime extension is iterative because adding a new liveness use
// may create new overlapping access scopes. This can happen because there is no
// guarantee of strict stack discpline across unrelated access. For example:
//
//     %def
//     begin_access A
//     use %def        // Initial pruned lifetime boundary
//     begin_access B
//     end_access A    // Lifetime boundary after first extension
//     end_access B    // Lifetime boundary after second extension
//     destroy %def
//
// If the lifetime extension did not iterate, then def would be destroyed within
// B's access scope when originally it was destroyed outside that scope.
void CanonicalizeOSSALifetime::extendLivenessThroughOverlappingAccess() {
  this->accessBlocks = accessBlockAnalysis->get(getCurrentDef()->getFunction());

  // Visit each original consuming use or destroy as the starting point for a
  // backward CFG traversal. This traversal must only visit blocks within the
  // original extended lifetime.
  bool changed = true;
  while (changed) {
    changed = false;
    blockWorklist.initializeRange(consumingBlocks);
    while (auto *bb = blockWorklist.pop()) {
      auto blockLiveness = liveness.getBlockLiveness(bb);
      // Ignore blocks within pruned liveness.
      if (blockLiveness == PrunedLiveBlocks::LiveOut) {
        continue;
      }
      if (blockLiveness == PrunedLiveBlocks::Dead) {
        // Continue searching upward to find the pruned liveness boundary.
        for (auto *predBB : bb->getPredecessorBlocks()) {
          blockWorklist.insert(predBB);
        }
        // Otherwise, ignore dead blocks with no nonlocal end_access.
        if (!accessBlocks->containsNonLocalEndAccess(bb)) {
          continue;
        }
      }
      bool blockHasUse = (blockLiveness == PrunedLiveBlocks::LiveWithin);
      // Find the latest partially overlapping access scope, if one exists:
      //     use %def // pruned liveness ends here
      //     end_access
      for (auto &inst : llvm::reverse(*bb)) {
        // Stop at the latest use. An earlier end_access does not overlap.
        if (blockHasUse && liveness.isInterestingUser(&inst)) {
          break;
        }
        if (endsAccessOverlappingPrunedBoundary(&inst)) {
          liveness.updateForUse(&inst, /*lifetimeEnding*/ false);
          changed = true;
          break;
        }
      }
      // If liveness changed, might as well restart CFG traversal.
      if (changed) {
        break;
      }
    }
  }
}

//===----------------------------------------------------------------------===//
// MARK: Step 2. Find the destroy points of the current def based on the pruned
// liveness computed in Step 1.
//===----------------------------------------------------------------------===//

/// The liveness boundary is at a CFG edge `predBB` -> `succBB`, meaning that
/// `currentDef` is live out of at least one other `predBB` successor.
///
/// Create and record a final destroy_value at the beginning of `succBB`
/// (assuming no critical edges).
void CanonicalizeOSSALifetime::insertDestroyOnCFGEdge(
  SILBasicBlock *predBB, SILBasicBlock *succBB, bool needsPoison) {

  assert(succBB->getSinglePredecessorBlock() == predBB
         && "value is live-out on another predBB successor: critical edge?");

  auto pos = succBB->begin();
  // TODO: to improve debugability, consider advancing the poison position ahead
  // of operations that are known not to access weak references.
  SILBuilderWithScope builder(pos);
  auto loc = RegularLocation::getAutoGeneratedLocation(pos->getLoc());
  auto *di = builder.createDestroyValue(loc, currentDef, needsPoison);
  instModCallbacks.createdNewInst(di);

  consumes.recordFinalConsume(di);

  ++NumDestroysGenerated;
  LLVM_DEBUG(llvm::dbgs() << "  Destroy on edge " << *di);
}

/// This liveness boundary is within a basic block at the given position.
///
/// Create a final destroy, immediately after `pos`.
static void insertDestroyAtInst(SILBasicBlock::iterator pos,
                                DestroyValueInst *existingDestroy, SILValue def,
                                bool needsPoison,
                                CanonicalOSSAConsumeInfo &consumes,
                                InstModCallbacks &callbacks) {
  if (existingDestroy) {
    for (; pos != existingDestroy->getIterator(); ++pos) {
      if (auto *debugVal = dyn_cast<DebugValueInst>(&*pos)) {
        consumes.popDebugAfterConsume(debugVal);
      }
    }
    consumes.recordFinalConsume(existingDestroy);
    // Avoid resetting poison just in case this runs twice.
    if (needsPoison) {
      existingDestroy->setPoisonRefs(true);
    }
    return;
  }
  SILBuilderWithScope builder(pos);
  auto loc = RegularLocation::getAutoGeneratedLocation((*pos).getLoc());
  auto *di = builder.createDestroyValue(loc, def, needsPoison);
  callbacks.createdNewInst(di);
  consumes.recordFinalConsume(di);

  ++NumDestroysGenerated;
  LLVM_DEBUG(llvm::dbgs() << "  Destroy at last use " << *di);
}

// The pruned liveness boundary is within the given basic block. Find the
// block's last use. If the last use consumes the value, record it as a
// destroy. Otherwise, insert a new destroy_value.
//
// TODO: This has become quite a hack. Instead, the final liveness boundary
// should be returned in a data structure along with summary information about
// each block. Then any special logic for handling existing destroys, debug
// values, and poison should be applied to that block summary which can provide
// the input to rewriteCopies.
void CanonicalizeOSSALifetime::findOrInsertDestroyInBlock(SILBasicBlock *bb) {
  auto *defInst = currentDef->getDefiningInstruction();
  DestroyValueInst *existingDestroy = nullptr;
  bool existingDestroyNeedsPoison = false;
  // needsPoison is true as soon as an existingDestroy is seen, but sticky.
  bool needsPoison = false;
  auto instIter = bb->getTerminator()->getIterator();
  while (true) {
    auto *inst = &*instIter;

    if (pruneDebugMode) {
      if (auto *dvi = dyn_cast<DebugValueInst>(inst)) {
        if (debugValues.erase(dvi))
          consumes.recordDebugAfterConsume(dvi);
      }
    }
    switch (liveness.isInterestingUser(inst)) {
    case PrunedLiveness::NonUser:
      break;
    case PrunedLiveness::NonLifetimeEndingUse:
      // Insert a destroy after this non-consuming use.
      if (isa<TermInst>(inst)) {
        for (auto &succ : bb->getSuccessors()) {
          insertDestroyOnCFGEdge(bb, succ, poisonRefsMode);
          setChanged();
        }
      } else {
        if (existingDestroy) {
          needsPoison = existingDestroyNeedsPoison;
        }
        insertDestroyAtInst(std::next(instIter), existingDestroy, currentDef,
                            needsPoison, consumes, instModCallbacks);
        setChanged();
      }
      return;
    case PrunedLiveness::LifetimeEndingUse:
      if (!needsPoison) {
        // This use becomes a final consume.
        consumes.recordFinalConsume(inst);
        return;
      }
      // If a destroy needs poison, simply make it so.
      auto *destroy = dyn_cast<DestroyValueInst>(inst);
      // Reuse an existing one if we need to.
      if (!destroy) {
        destroy = existingDestroy;
        needsPoison = existingDestroyNeedsPoison;
      }
      if (destroy) {
        destroy->setPoisonRefs(needsPoison);
        consumes.recordFinalConsume(destroy);
        return;
      }
      // Put this in the set of final consumes that need poison injection.
      consumes.recordNeedsPoison(inst);
      return;
    }
    // This is not a potential last user. Keep scanning.
    // Allow lifetimes to be artificially extended up to the next call. The goal
    // is to prevent repeated destroy rewriting without inhibiting optimization.
    if (ApplySite::isa(inst)) {
      existingDestroy = nullptr;
    } else if (!existingDestroy) {
      if (auto *destroy = dyn_cast<DestroyValueInst>(inst)) {
        auto destroyDef = CanonicalizeOSSALifetime::getCanonicalCopiedDef(
            destroy->getOperand());
        if (destroyDef == currentDef) {
          existingDestroy = destroy;
          // If this destroy is reused, it is not poisoned.
          existingDestroyNeedsPoison = needsPoison;
          if (poisonRefsMode) {
            // Any earlier consume will be poisoned.
            needsPoison = true;
          }
        }
      }
    }
    if (instIter == bb->begin()) {
      assert(cast<SILArgument>(currentDef)->getParent() == bb);
      if (existingDestroy) {
        needsPoison = existingDestroyNeedsPoison;
      }
      insertDestroyAtInst(instIter, existingDestroy, currentDef, needsPoison,
                          consumes, instModCallbacks);
      setChanged();
      return;
    }
    --instIter;
    // If the original def is reached, this is a dead live range. Insert a
    // destroy immediately after the def.
    if (&*instIter == defInst) {
      if (existingDestroy) {
        needsPoison = existingDestroyNeedsPoison;
      }
      insertDestroyAtInst(std::next(instIter), existingDestroy, currentDef,
                          needsPoison, consumes, instModCallbacks);
      setChanged();
      return;
    }
  }
}

/// Populate `consumes` with the final destroy points once copies are
/// eliminated. This only applies to owned values.
///
/// Observations:
/// - currentDef must be postdominated by some subset of its
///   consuming uses, including destroys on all return paths.
/// - The postdominating consumes cannot be within nested loops.
/// - Any blocks in nested loops are now marked LiveOut.
void CanonicalizeOSSALifetime::findOrInsertDestroys() {
  this->accessBlocks = accessBlockAnalysis->get(getCurrentDef()->getFunction());

  // Visit each original consuming use or destroy as the starting point for a
  // backward CFG traversal.
  blockWorklist.initializeRange(consumingBlocks);
  while (auto *bb = blockWorklist.pop()) {
    // Process each block that has not been visited and is not LiveOut.
    switch (liveness.getBlockLiveness(bb)) {
    case PrunedLiveBlocks::LiveOut:
      // A lifetimeEndBlock may be determined to be LiveOut after analyzing the
      // extended  It is irrelevent for finding the boundary.
      break;
    case PrunedLiveBlocks::LiveWithin: {
      // The liveness boundary is inside this block. Insert a final destroy
      // inside the block if it doesn't already have one.
      findOrInsertDestroyInBlock(bb);
      break;
    }
    case PrunedLiveBlocks::Dead:
      // Continue searching upward to find the pruned liveness boundary.
      for (auto *predBB : bb->getPredecessorBlocks()) {
        if (liveness.getBlockLiveness(predBB) == PrunedLiveBlocks::LiveOut) {
          insertDestroyOnCFGEdge(predBB, bb, poisonRefsMode);
          setChanged();
        } else {
          if (poisonRefsMode) {
            remnantLiveOutBlocks.insert(predBB);
          }
          blockWorklist.insert(predBB);
        }
      }
      break;
    }
  }
}

//===----------------------------------------------------------------------===//
// MARK: Step 3. Rewrite copies and destroys
//===----------------------------------------------------------------------===//

/// Revisit the def-use chain of currentDef. Mark unneeded original
/// copies and destroys for deletion. Insert new copies for interior uses that
/// require ownership of the used operand.
void CanonicalizeOSSALifetime::rewriteCopies() {
  bool isOwned = currentDef.getOwnershipKind() == OwnershipKind::Owned;
  assert((!isOwned || !consumes.hasPersistentCopies())
         && "persistent copies use borrowed values");

  SmallSetVector<SILInstruction *, 8> instsToDelete;
  defUseWorklist.clear();

  // Visit each operand in the def-use chain.
  //
  // Return true if the operand can use the current definition. Return false if
  // it requires a copy.
  auto visitUse = [&](Operand *use) {
    auto *user = use->getUser();
    // Recurse through copies.
    if (auto *copy = dyn_cast<CopyValueInst>(user)) {
      if (!consumes.isPersistentCopy(copy)) {
        defUseWorklist.insert(copy);
        return true;
      }
    }
    if (auto *destroy = dyn_cast<DestroyValueInst>(user)) {
      // If this destroy was marked as a final destroy, ignore it; otherwise,
      // delete it.
      if (!consumes.claimConsume(destroy)) {
        instsToDelete.insert(destroy);
        LLVM_DEBUG(llvm::dbgs() << "  Removing " << *destroy);
        ++NumDestroysEliminated;
      }
      // If another destroy is reachable on this path, then poison this
      // destroy. It will already be poisoned if it was inserted on a CFG edge
      // or another destroy occurs later in the same block.
      if (!destroy->poisonRefs()
          && remnantLiveOutBlocks.count(destroy->getParent())) {
        destroy->setPoisonRefs(true);
      }
      return true;
    }

    // Nonconsuming uses do not need copies and cannot be marked as destroys.
    // A lifetime-ending use here must be a consume because EndBorrow/Reborrow
    // uses have been filtered out.
    if (!use->isLifetimeEnding())
      return true;

    // If this use was not marked as a final destroy *or* this is not the first
    // consumed operand we visited, then it needs a copy.
    if (!consumes.claimConsume(user))
      return false;

    // Final consumes that need poison, also need a copy.
    if (consumes.needsPoison(user))
      return false;

    // If another destroy is reachable on this path, then this consume needs
    // poison even though findOrInsertDestroyInBlock didn't know that.
    if (remnantLiveOutBlocks.count(user->getParent())) {
      consumes.recordNeedsPoison(user);
      return false;
    }
    return true;
  };

  // Perform a def-use traversal, visiting each use operand.
  for (auto useIter = currentDef->use_begin(), endIter = currentDef->use_end();
       useIter != endIter;) {
    Operand *use = *useIter++;
    // A direct lifetime-ending use of a guaranteed value (EndBorrow or
    // Reborrow), never needs a copy.
    if (!isOwned && use->isLifetimeEnding()) {
      continue;
    }
    if (!visitUse(use)) {
      copyLiveUse(use, instModCallbacks);
      setChanged();
    }
  }
  while (SILValue value = defUseWorklist.pop()) {
    CopyValueInst *srcCopy = cast<CopyValueInst>(value);
    // Recurse through copies while replacing their uses.
    Operand *reusedCopyOp = nullptr;
    for (auto useIter = srcCopy->use_begin(); useIter != srcCopy->use_end();) {
      Operand *use = *useIter++;
      if (!visitUse(use)) {
        if (!reusedCopyOp && srcCopy->getParent() == use->getParentBlock()) {
          reusedCopyOp = use;
        } else {
          copyLiveUse(use, instModCallbacks);
          setChanged();
        }
      }
    }
    if (!(reusedCopyOp && srcCopy->hasOneUse())) {
      setChanged();
      instModCallbacks.replaceValueUsesWith(srcCopy, srcCopy->getOperand());
      if (reusedCopyOp) {
        instModCallbacks.setUseValue(reusedCopyOp, srcCopy);
      } else {
        if (instsToDelete.insert(srcCopy)) {
          LLVM_DEBUG(llvm::dbgs() << "  Removing " << *srcCopy);
          ++NumCopiesEliminated;
        }
      }
    }
  }
  assert(!consumes.hasUnclaimedConsumes());

  // Insert destroys wherever poison is needed. This may recover more debug
  // values, erasing them from the debugValues set.
  injectPoison();

  // Add any debug_values from Dead blocks into the debugAfterConsume set.
  for (auto *dvi : debugValues) {
    if (liveness.getBlockLiveness(dvi->getParent()) == PrunedLiveBlocks::Dead) {
      consumes.recordDebugAfterConsume(dvi);
    }
  }

  // Remove any dead, non-recovered debug_values.
  for (auto *dvi : consumes.getDebugInstsAfterConsume()) {
    LLVM_DEBUG(llvm::dbgs() << "  Removing debug_value: " << *dvi);
    instModCallbacks.deleteInst(dvi);
  }

  // Remove the leftover copy_value and destroy_value instructions.
  if (!instsToDelete.empty()) {
    recursivelyDeleteTriviallyDeadInstructions(instsToDelete.takeVector(),
                                               /*force=*/true,
                                               instModCallbacks);
    setChanged();
  }
}

/// Insert poison destroys after each consume that needs poison.
void CanonicalizeOSSALifetime::injectPoison() {
  for (SILInstruction *consume : consumes.getNeedsPoisonConsumes()) {
    auto createDestroy = [&](SILBuilder &builder) {
      auto loc = RegularLocation::getAutoGeneratedLocation(
        builder.getInsertionPoint()->getLoc());
      auto *di = builder.createDestroyValue(loc, currentDef,
                                            /*needsPoison*/ true);
      instModCallbacks.createdNewInst(di);
      ++NumDestroysGenerated;
      LLVM_DEBUG(llvm::dbgs() << "  Destroy at last use " << *di);
    };
    if (auto *branch = dyn_cast<BranchInst>(consume)) {
      // At a phi, destroy the value before branching.
      //
      // A copy must have been created for the branch operand during
      // rewriteCopies (but there's no easy way to assert that here).
      SILBuilderWithScope builder(branch);
      createDestroy(builder);
    } else {
      // For normal instructions and non-phi block terminators, destroy the
      // value after the operation.
      SILBuilderWithScope::insertAfter(consume, createDestroy);
    }
  }
}

//===----------------------------------------------------------------------===//
//                            MARK: Top-Level API
//===----------------------------------------------------------------------===//

/// True if \p def should be canonicalized in poisonRefs mode.
///
/// Currently, we only handle owned values because, for now, the goal is to
/// shorten lifetimes to mimic -O behavior, not to remove copies.
///
/// IRGen must also have support for injecting poison into values of this type.
bool shouldCanonicalizeWithPoison(SILValue def) {
  assert(def->getType().isObject() && "only SIL values are canonicalized");
  auto objectTy = def->getType().unwrapOptionalType();

  // TODO: Handle structs, enums, and tuples.
  //
  // TODO: Functions are not currently handled because of closure lifetime
  // bugs. Noescape closures don't always have a dependence.
  return objectTy.isAnyClassReferenceType();
}

bool CanonicalizeOSSALifetime::canonicalizeValueLifetime(SILValue def) {
  LLVM_DEBUG(llvm::dbgs() << "  Canonicalizing: " << def);

  switch (def.getOwnershipKind()) {
  case OwnershipKind::None:
  case OwnershipKind::Unowned:
  case OwnershipKind::Any:
    return false;
  case OwnershipKind::Guaranteed:
    // The goal of poisonRefsMode is only to hoist destroys, not remove copies.
    if (poisonRefsMode)
      return false;

    initDef(def);
    if (!computeBorrowLiveness()) {
      clearLiveness();
      return false;
    }
    // Set outerCopy and persistentCopies and rewrite uses
    // outside the scope.
    if (!consolidateBorrowScope()) {
      clearLiveness();
      return false;
    }
    // Invalidate book-keeping before deleting instructions.
    clearLiveness();
    // Rewrite copies and delete extra destroys within the scope.
    assert(!consumes.hasFinalConsumes());
    rewriteCopies();
    return true;
  case OwnershipKind::Owned:
    if (poisonRefsMode && !shouldCanonicalizeWithPoison(def))
      return false;

    initDef(def);
    // Step 1: compute liveness
    if (!computeCanonicalLiveness()) {
      clearLiveness();
      return false;
    }
    extendLivenessThroughOverlappingAccess();
    // Step 2: record final destroys
    findOrInsertDestroys();
    // Step 3: rewrite copies and delete extra destroys
    rewriteCopies();

    clearLiveness();
    consumes.clear();
    return true;
  }
  llvm_unreachable("covered switch");
}

//===----------------------------------------------------------------------===//
//                              MARK: Debugging
//===----------------------------------------------------------------------===//

SWIFT_ASSERT_ONLY_DECL(
  void CanonicalOSSAConsumeInfo::dump() const {
    llvm::dbgs() << "Consumes:";
    for (auto &blockAndInst : finalBlockConsumes) {
      llvm::dbgs() << "  " << *blockAndInst.getSecond();
    }
  })

//===----------------------------------------------------------------------===//
//                    MARK: Canonicalize Lifetimes Utility
//===----------------------------------------------------------------------===//

SILAnalysis::InvalidationKind
swift::canonicalizeOSSALifetimes(CanonicalizeOSSALifetime &canonicalizer,
                                 ArrayRef<SILValue> copiedDefs) {
  auto isCopyDead = [](CopyValueInst *copy, bool pruneDebug) -> bool {
    for (Operand *use : copy->getUses()) {
      auto *user = use->getUser();
      if (isa<DestroyValueInst>(user)) {
        continue;
      }
      if (pruneDebug && isa<DebugValueInst>(user)) {
        continue;
      }
      return false;
    }
    return true;
  };

  // Cleanup dead copies. If getCanonicalCopiedDef returns a copy (because the
  // copy's source operand is unrecgonized), then the copy is itself treated
  // like a def and may be dead after canonicalization.
  SmallVector<SILInstruction *, 4> deadCopies;
  for (auto def : copiedDefs) {
    // Canonicalized this def. If we did not perform any canonicalization, just
    // continue.
    if (!canonicalizer.canonicalizeValueLifetime(def))
      continue;

    // Otherwise, see if we have a dead copy.
    if (auto *copy = dyn_cast<CopyValueInst>(def)) {
      if (isCopyDead(copy, false /*prune debug*/)) {
        deadCopies.push_back(copy);
      }
    }

    // Canonicalize any new outer copy.
    if (SILValue outerCopy = canonicalizer.createdOuterCopy()) {
      SILValue outerDef = canonicalizer.getCanonicalCopiedDef(outerCopy);
      canonicalizer.canonicalizeValueLifetime(outerDef);
    }

    // TODO: also canonicalize any lifetime.persistentCopies like separate owned
    // live ranges.
  }

  if (!canonicalizer.hasChanged() && deadCopies.empty()) {
    return SILAnalysis::InvalidationKind::Nothing;
  }

  // We use our canonicalizers inst mod callbacks.
  InstructionDeleter deleter(canonicalizer.getInstModCallbacks());
  for (auto *copy : deadCopies) {
    deleter.deleteIfDead(copy);
  }
  return SILAnalysis::InvalidationKind::Instructions;
}
